Difference Operator
   HOME

TheInfoList



OR:

In
mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, a recurrence relation is an
equation In mathematics, an equation is a formula that expresses the equality of two expressions, by connecting them with the equals sign . The word ''equation'' and its cognates in other languages may have subtly different meanings; for example, in ...
according to which the nth term of a
sequence In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is calle ...
of numbers is equal to some combination of the previous terms. Often, only k previous terms of the sequence appear in the equation, for a parameter k that is independent of n; this number k is called the ''order'' of the relation. If the values of the first k numbers in the sequence have been given, the rest of the sequence can be calculated by repeatedly applying the equation. In ''linear recurrences'', the th term is equated to a
linear function In mathematics, the term linear function refers to two distinct but related notions: * In calculus and related areas, a linear function is a function (mathematics), function whose graph of a function, graph is a straight line, that is, a polynomia ...
of the k previous terms. A famous example is the recurrence for the
Fibonacci number In mathematics, the Fibonacci numbers, commonly denoted , form a sequence, the Fibonacci sequence, in which each number is the sum of the two preceding ones. The sequence commonly starts from 0 and 1, although some authors start the sequence from ...
s, F_n=F_+F_ where the order k is two and the linear function merely adds the two previous terms. This example is a
linear recurrence with constant coefficients In mathematics (including combinatorics, linear algebra, and dynamical systems), a linear recurrence with constant coefficients (also known as a linear recurrence relation or linear difference equation) sets equal to 0 a polynomial that is linear ...
, because the coefficients of the linear function (1 and 1) are constants that do not depend on n. For these recurrences, one can express the general term of the sequence as a
closed-form expression In mathematics, a closed-form expression is a mathematical expression that uses a finite number of standard operations. It may contain constants, variables, certain well-known operations (e.g., + − × ÷), and functions (e.g., ''n''th roo ...
of n. As well, linear recurrences with polynomial coefficients depending on n are also important, because many common elementary and
special Special or specials may refer to: Policing * Specials, Ulster Special Constabulary, the Northern Ireland police force * Specials, Special Constable, an auxiliary, volunteer, or temporary; police worker or police officer Literature * ''Specia ...
functions have a
Taylor series In mathematics, the Taylor series or Taylor expansion of a function is an infinite sum of terms that are expressed in terms of the function's derivatives at a single point. For most common functions, the function and the sum of its Taylor serie ...
whose coefficients satisfy such a recurrence relation (see
holonomic function In mathematics, and more specifically in analysis, a holonomic function is a smooth function of several variables that is a solution of a system of linear homogeneous differential equations with polynomial coefficients and satisfies a suitable d ...
). Solving a recurrence relation means obtaining a
closed-form solution In mathematics, a closed-form expression is a mathematical expression that uses a finite number of standard operations. It may contain constants, variables, certain well-known operations (e.g., + − × ÷), and functions (e.g., ''n''th roo ...
: a non-recursive function of n. The concept of a recurrence relation can be extended to
multidimensional array In computer science, array is a data type that represents a collection of ''elements'' (values or variables), each selected by one or more indices (identifying keys) that can be computed at run time during program execution. Such a collection ...
s, that is,
indexed families In mathematics, a family, or indexed family, is informally a collection of objects, each associated with an index from some index set. For example, a ''family of real numbers, indexed by the set of integers'' is a collection of real numbers, whe ...
that are indexed by
tuple In mathematics, a tuple is a finite ordered list (sequence) of elements. An -tuple is a sequence (or ordered list) of elements, where is a non-negative integer. There is only one 0-tuple, referred to as ''the empty tuple''. An -tuple is defi ...
s of
natural number In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country"). Numbers used for counting are called ''Cardinal n ...
s.


Definition

A ''recurrence relation'' is an equation that expresses each element of a
sequence In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is calle ...
as a function of the preceding ones. More precisely, in the case where only the immediately preceding element is involved, a recurrence relation has the form :u_n=\varphi(n, u_)\quad\text\quad n>0, where :\varphi:\mathbb N\times X \to X is a function, where is a set to which the elements of a sequence must belong. For any u_0\in X, this defines a unique sequence with u_0 as its first element, called the ''initial value''. It is easy to modify the definition for getting sequences starting from the term of index 1 or higher. This defines recurrence relation of ''first order''. A recurrence relation of ''order'' has the form :u_n=\varphi(n, u_, u_, \ldots, u_)\quad\text\quad n\ge k, where \varphi: \mathbb N\times X^k \to X is a function that involves consecutive elements of the sequence. In this case, initial values are needed for defining a sequence.


Examples


Factorial

The
factorial In mathematics, the factorial of a non-negative denoted is the product of all positive integers less than or equal The factorial also equals the product of n with the next smaller factorial: \begin n! &= n \times (n-1) \times (n-2) \t ...
is defined by the recurrence relation :n!=n(n-1)!\quad\text\quad n>0, and the initial condition :0!=1. This is an example of a ''linear recurrence with polynomial coefficients'' of order 1, with the simple polynomial :f(n)=n as its only coefficient.


Logistic map

An example of a recurrence relation is the
logistic map The logistic map is a polynomial mapping (equivalently, recurrence relation) of degree 2, often referred to as an archetypal example of how complex, chaotic behaviour can arise from very simple non-linear dynamical equations. The map was popular ...
: :x_ = r x_n (1 - x_n), with a given constant r; given the initial term x_0 each subsequent term is determined by this relation.


Fibonacci numbers

The recurrence of order two satisfied by the
Fibonacci number In mathematics, the Fibonacci numbers, commonly denoted , form a sequence, the Fibonacci sequence, in which each number is the sum of the two preceding ones. The sequence commonly starts from 0 and 1, although some authors start the sequence from ...
s is the canonical example of a homogeneous
linear recurrence In mathematics (including combinatorics, linear algebra, and dynamical systems), a linear recurrence with constant coefficients (also known as a linear recurrence relation or linear difference equation) sets equal to 0 a polynomial that is linear ...
relation with constant coefficients (see below). The Fibonacci sequence is defined using the recurrence :F_n = F_+F_ with
initial condition In mathematics and particularly in dynamic systems, an initial condition, in some contexts called a seed value, is a value of an evolving variable at some point in time designated as the initial time (typically denoted ''t'' = 0). For ...
s :F_0 = 0 :F_1 = 1. Explicitly, the recurrence yields the equations :F_2 = F_1 + F_0 :F_3 = F_2 + F_1 :F_4 = F_3 + F_2 etc. We obtain the sequence of Fibonacci numbers, which begins :0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... The recurrence can be solved by methods described below yielding
Binet's formula In mathematics, the Fibonacci numbers, commonly denoted , form a sequence, the Fibonacci sequence, in which each number is the sum of the two preceding ones. The sequence commonly starts from 0 and 1, although some authors start the sequence from ...
, which involves powers of the two roots of the characteristic polynomial t^2 = t + 1; the
generating function In mathematics, a generating function is a way of encoding an infinite sequence of numbers () by treating them as the coefficients of a formal power series. This series is called the generating function of the sequence. Unlike an ordinary seri ...
of the sequence is the
rational function In mathematics, a rational function is any function that can be defined by a rational fraction, which is an algebraic fraction such that both the numerator and the denominator are polynomials. The coefficients of the polynomials need not be rat ...
: \frac.


Binomial coefficients

A simple example of a multidimensional recurrence relation is given by the
binomial coefficient In mathematics, the binomial coefficients are the positive integers that occur as coefficients in the binomial theorem. Commonly, a binomial coefficient is indexed by a pair of integers and is written \tbinom. It is the coefficient of the t ...
s \tbinom, which count the ways of selecting k elements out of a set of n elements. They can be computed by the recurrence relation :\binom=\binom+\binom, with the base cases \tbinom=\tbinom=1. Using this formula to compute the values of all binomial coefficients generates an infinite array called
Pascal's triangle In mathematics, Pascal's triangle is a triangular array of the binomial coefficients that arises in probability theory, combinatorics, and algebra. In much of the Western world, it is named after the French mathematician Blaise Pascal, although ot ...
. The same values can also be computed directly by a different formula that is not a recurrence, but uses
factorial In mathematics, the factorial of a non-negative denoted is the product of all positive integers less than or equal The factorial also equals the product of n with the next smaller factorial: \begin n! &= n \times (n-1) \times (n-2) \t ...
s, multiplication and division, not just additions: :\binom=\frac. The binomial coefficients can also be computed with a uni-dimensional recurrence: :\binom n k = \binom n(n-k+1)/k, with the initial value \binom n 0 =1 (The division is not displayed as a fraction for emphasizing that it must be computed after the multiplication, for not introducing fractional numbers). This recurrence is widely used in computers because it does not require to build a table as does the bi-dimensional recurrence, and does involve very large integers as does the formula with factorials (if one uses \binom nk= \binom n, all involved integers are smaller than the final result).


Difference operator and difference equations

The is an operator that maps
sequence In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is calle ...
s to sequences, and, more generally, functions to functions. It is commonly denoted \Delta, and is defined, in
functional notation In mathematics, a function from a set to a set assigns to each element of exactly one element of .; the words map, mapping, transformation, correspondence, and operator are often used synonymously. The set is called the domain of the functi ...
, as :(\Delta f)(x)=f(x+1)-f(x). It is thus a special case of
finite difference A finite difference is a mathematical expression of the form . If a finite difference is divided by , one gets a difference quotient. The approximation of derivatives by finite differences plays a central role in finite difference methods for t ...
. When using the index notation for sequences, the definition becomes :(\Delta a)_n= a_ - a_n. The parentheses around \Delta f and \Delta a are generally omitted, and \Delta a_n must be understood as the term of index in the sequence \Delta a, and not \Delta applied to the element a_n. Given
sequence In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is calle ...
a=(a_n)_, the of is \Delta a. The is \Delta^2 a=(\Delta\circ\Delta)a= \Delta(\Delta a). A simple computation shows that :\Delta^2 a_n= a_ - 2a_ + a_n. More generally: the ''th difference'' is defined recursively as \Delta^k=\Delta\circ \Delta^, and one has :\Delta^k a_n = \sum_^k (-1)^t \binom a_. This relation can be inverted, giving :a_ = a_n + \Delta a_n + \cdots + \Delta^k(a_n). A of order is an equation that involves the first differences of a sequence or a function, in the same way as a
differential equation In mathematics, a differential equation is an equation that relates one or more unknown functions and their derivatives. In applications, the functions generally represent physical quantities, the derivatives represent their rates of change, an ...
of order relates the first
derivative In mathematics, the derivative of a function of a real variable measures the sensitivity to change of the function value (output value) with respect to a change in its argument (input value). Derivatives are a fundamental tool of calculus. F ...
s of a function. The two above relations allow transforming a recurrence relation of order into a difference equation of order , and, conversely, a difference equation of order into recurrence relation of order . Each transformation is the inverse of the other, and the sequences that are solution of the difference equation are exactly those that satisfies the recurrence relation. For example, the difference equation :3\Delta^2 a_n + 2\Delta a_n + 7a_n = 0 is equivalent to the recurrence relation :3a_ = 4a_ - 8a_n, in the sense that the two equations are satisfied by the same sequences. As it is equivalent for a sequence to satisfy a recurrence relation or to be the solution of a difference equation, the two terms "recurrence relation" and "difference equation" are sometimes used interchangeably. See
Rational difference equation A rational difference equation is a nonlinear difference equation of the form : x_ = \frac~, where the initial conditions x_, x_,\dots, x_ are such that the denominator never vanishes for any . First-order rational difference equation A first-orde ...
and
Matrix difference equation A matrix difference equation is a difference equation in which the value of a vector (or sometimes, a matrix) of variables at one point in time is related to its own value at one or more previous points in time, using matrices. The order of the eq ...
for example of uses of "difference equation" instead of "recurrence relation" Difference equations resemble to differential equations, and this resemblance is often used to mimic methods for solving differentiable equations to apply to solving difference equations, and therefore recurrence relations.
Summation equation In mathematics, a summation equation or discrete integral equation is an equation in which an unknown function appears under a summation sign. The theories of summation equations and integral equations can be unified as ''integral equations on tim ...
s relate to difference equations as
integral equation In mathematics, integral equations are equations in which an unknown Function (mathematics), function appears under an integral sign. In mathematical notation, integral equations may thus be expressed as being of the form: f(x_1,x_2,x_3,...,x_n ; ...
s relate to differential equations. See
time scale calculus In mathematics, time-scale calculus is a unification of the theory of difference equations with that of differential equations, unifying integral and differential calculus with the calculus of finite differences, offering a formalism for studying hy ...
for a unification of the theory of difference equations with that of differential equations.


From sequences to grids

Single-variable or one-dimensional recurrence relations are about sequences (i.e. functions defined on one-dimensional grids). Multi-variable or n-dimensional recurrence relations are about n-dimensional grids. Functions defined on n-grids can also be studied with partial difference equations.


Solving


Solving linear recurrence relations with constant coefficients


Solving first-order non-homogeneous recurrence relations with variable coefficients

Moreover, for the general first-order non-homogeneous linear recurrence relation with variable coefficients: :a_ = f_n a_n + g_n, \qquad f_n \neq 0, there is also a nice method to solve it: :a_ - f_n a_n = g_n :\frac - \frac = \frac :\frac - \frac = \frac Let :A_n = \frac, Then :A_ - A_n = \frac :\sum_^(A_ - A_m) = A_n - A_0 = \sum_^\frac :\frac = A_0 + \sum_^\frac :a_n = \left(\prod_^ f_k \right) \left(A_0 + \sum_^\frac\right) If we apply the formula to a_ = (1 + h f_) a_n + hg_ and take the limit h \to 0, we get the formula for first order
linear differential equation In mathematics, a linear differential equation is a differential equation that is defined by a linear polynomial in the unknown function and its derivatives, that is an equation of the form :a_0(x)y + a_1(x)y' + a_2(x)y'' \cdots + a_n(x)y^ = b( ...
s with variable coefficients; the sum becomes an integral, and the product becomes the exponential function of an integral.


Solving general homogeneous linear recurrence relations

Many homogeneous linear recurrence relations may be solved by means of the
generalized hypergeometric series In mathematics, a generalized hypergeometric series is a power series in which the ratio of successive coefficients indexed by ''n'' is a rational function of ''n''. The series, if convergent, defines a generalized hypergeometric function, which ...
. Special cases of these lead to recurrence relations for the
orthogonal polynomials In mathematics, an orthogonal polynomial sequence is a family of polynomials such that any two different polynomials in the sequence are orthogonality, orthogonal to each other under some inner product. The most widely used orthogonal polynomial ...
, and many
special function Special functions are particular mathematical functions that have more or less established names and notations due to their importance in mathematical analysis, functional analysis, geometry, physics, or other applications. The term is defined by ...
s. For example, the solution to :J_=\fracJ_n-J_ is given by :J_n=J_n(z), the
Bessel function Bessel functions, first defined by the mathematician Daniel Bernoulli and then generalized by Friedrich Bessel, are canonical solutions of Bessel's differential equation x^2 \frac + x \frac + \left(x^2 - \alpha^2 \right)y = 0 for an arbitrary ...
, while :(b-n)M_ +(2n-b+z)M_n - nM_=0 is solved by :M_n=M(n,b;z) the
confluent hypergeometric series In mathematics, a confluent hypergeometric function is a solution of a confluent hypergeometric equation, which is a degenerate form of a hypergeometric differential equation where two of the three regular singularities merge into an irregular ...
. Sequences which are the solutions of linear difference equations with polynomial coefficients are called P-recursive. For these specific recurrence equations algorithms are known which find
polynomial In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An exa ...
,
rational Rationality is the quality of being guided by or based on reasons. In this regard, a person acts rationally if they have a good reason for what they do or a belief is rational if it is based on strong evidence. This quality can apply to an abi ...
or hypergeometric solutions.


Solving first-order rational difference equations

A first order rational difference equation has the form w_ = \tfrac. Such an equation can be solved by writing w_t as a nonlinear transformation of another variable x_t which itself evolves linearly. Then standard methods can be used to solve the linear difference equation in x_t.


Stability


Stability of linear higher-order recurrences

The linear recurrence of order d, :a_n = c_1a_ + c_2a_+\cdots+c_da_, has the characteristic equation :\lambda^d - c_1 \lambda^ - c_2 \lambda^ - \cdots - c_d \lambda^0 =0. The recurrence is
stable A stable is a building in which livestock, especially horses, are kept. It most commonly means a building that is divided into separate stalls for individual animals and livestock. There are many different types of stables in use today; the ...
, meaning that the iterates converge asymptotically to a fixed value, if and only if the
eigenvalues In linear algebra, an eigenvector () or characteristic vector of a linear transformation is a nonzero vector that changes at most by a scalar factor when that linear transformation is applied to it. The corresponding eigenvalue, often denoted b ...
(i.e., the roots of the characteristic equation), whether real or complex, are all less than
unity Unity may refer to: Buildings * Unity Building, Oregon, Illinois, US; a historic building * Unity Building (Chicago), Illinois, US; a skyscraper * Unity Buildings, Liverpool, UK; two buildings in England * Unity Chapel, Wyoming, Wisconsin, US; a h ...
in absolute value.


Stability of linear first-order matrix recurrences

In the first-order matrix difference equation : _t - x^*= A _-x^*/math> with state vector x and transition matrix A, x converges asymptotically to the steady state vector x^* if and only if all eigenvalues of the transition matrix A (whether real or complex) have an
absolute value In mathematics, the absolute value or modulus of a real number x, is the non-negative value without regard to its sign. Namely, , x, =x if is a positive number, and , x, =-x if x is negative (in which case negating x makes -x positive), an ...
which is less than 1.


Stability of nonlinear first-order recurrences

Consider the nonlinear first-order recurrence :x_n=f(x_). This recurrence is locally stable, meaning that it converges to a fixed point x^* from points sufficiently close to x^*, if the slope of f in the neighborhood of x^* is smaller than
unity Unity may refer to: Buildings * Unity Building, Oregon, Illinois, US; a historic building * Unity Building (Chicago), Illinois, US; a skyscraper * Unity Buildings, Liverpool, UK; two buildings in England * Unity Chapel, Wyoming, Wisconsin, US; a h ...
in absolute value: that is, : , f' (x^*) , < 1. A nonlinear recurrence could have multiple fixed points, in which case some fixed points may be locally stable and others locally unstable; for continuous ''f'' two adjacent fixed points cannot both be locally stable. A nonlinear recurrence relation could also have a cycle of period k for k > 1. Such a cycle is stable, meaning that it attracts a set of initial conditions of positive measure, if the composite function :g(x) := f \circ f \circ \cdots \circ f(x) with f appearing k times is locally stable according to the same criterion: : , g' (x^*) , < 1, where x^* is any point on the cycle. In a
chaotic Chaotic was originally a Danish trading card game. It expanded to an online game in America which then became a television program based on the game. The program was able to be seen on 4Kids TV (Fox affiliates, nationwide), Jetix, The CW4Kid ...
recurrence relation, the variable x stays in a bounded region but never converges to a fixed point or an attracting cycle; any fixed points or cycles of the equation are unstable. See also
logistic map The logistic map is a polynomial mapping (equivalently, recurrence relation) of degree 2, often referred to as an archetypal example of how complex, chaotic behaviour can arise from very simple non-linear dynamical equations. The map was popular ...
,
dyadic transformation The dyadic transformation (also known as the dyadic map, bit shift map, 2''x'' mod 1 map, Bernoulli map, doubling map or sawtooth map) is the mapping (i.e., recurrence relation) : T: , 1) \to , 1)^\infty : x \mapsto (x_0, x_1, x_2, ...
, and tent map.


Relationship to differential equations

When solving an ordinary differential equation numerical ordinary differential equations, numerically, one typically encounters a recurrence relation. For example, when solving the initial value problem :y'(t) = f(t,y(t)), \ \ y(t_0)=y_0, with
Euler's method In mathematics and computational science, the Euler method (also called forward Euler method) is a first-order numerical procedure for solving ordinary differential equations (ODEs) with a given initial value. It is the most basic explicit met ...
and a step size h, one calculates the values :y_0=y(t_0), \ \ y_1=y(t_0+h), \ \ y_2=y(t_0+2h), \ \dots by the recurrence :\, y_ = y_n + hf(t_n,y_n), t_n = t_0 + nh Systems of linear first order differential equations can be discretized exactly analytically using the methods shown in the
discretization In applied mathematics, discretization is the process of transferring continuous functions, models, variables, and equations into discrete counterparts. This process is usually carried out as a first step toward making them suitable for numerical ...
article.


Applications


Mathematical biology

Some of the best-known difference equations have their origins in the attempt to model
population dynamics Population dynamics is the type of mathematics used to model and study the size and age composition of populations as dynamical systems. History Population dynamics has traditionally been the dominant branch of mathematical biology, which has ...
. For example, the
Fibonacci number In mathematics, the Fibonacci numbers, commonly denoted , form a sequence, the Fibonacci sequence, in which each number is the sum of the two preceding ones. The sequence commonly starts from 0 and 1, although some authors start the sequence from ...
s were once used as a model for the growth of a rabbit population. The
logistic map The logistic map is a polynomial mapping (equivalently, recurrence relation) of degree 2, often referred to as an archetypal example of how complex, chaotic behaviour can arise from very simple non-linear dynamical equations. The map was popular ...
is used either directly to model population growth, or as a starting point for more detailed models of population dynamics. In this context, coupled difference equations are often used to model the interaction of two or more
population Population typically refers to the number of people in a single area, whether it be a city or town, region, country, continent, or the world. Governments typically quantify the size of the resident population within their jurisdiction using a ...
s. For example, the
Nicholson–Bailey model The Nicholson–Bailey model was developed in the 1930s to describe the population dynamics of a coupled host- parasitoid system. It is named after Alexander John Nicholson and Victor Albert Bailey. Host-parasite and prey-predator systems can a ...
for a host-
parasite Parasitism is a close relationship between species, where one organism, the parasite, lives on or inside another organism, the host, causing it some harm, and is adapted structurally to this way of life. The entomologist E. O. Wilson has ...
interaction is given by :N_ = \lambda N_t e^ :P_ = N_t(1-e^), with N_t representing the hosts, and P_t the parasites, at time t.
Integrodifference equation In mathematics, an integrodifference equation is a recurrence relation on a function space, of the following form: : n_(x) = \int_ k(x, y)\, f(n_t(y))\, dy, where \\, is a sequence in the function space and \Omega\, is the domain of those funct ...
s are a form of recurrence relation important to spatial
ecology Ecology () is the study of the relationships between living organisms, including humans, and their physical environment. Ecology considers organisms at the individual, population, community, ecosystem, and biosphere level. Ecology overlaps wi ...
. These and other difference equations are particularly suited to modeling
univoltine Voltinism is a term used in biology to indicate the number of broods or generations of an organism in a year. The term is most often applied to insects, and is particularly in use in sericulture, where silkworm varieties vary in their voltinism. ...
populations.


Computer science

Recurrence relations are also of fundamental importance in
analysis of algorithms In computer science, the analysis of algorithms is the process of finding the computational complexity of algorithms—the amount of time, storage, or other resources needed to execute them. Usually, this involves determining a function that re ...
. If an
algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...
is designed so that it will break a problem into smaller subproblems ( divide and conquer), its running time is described by a recurrence relation. A simple example is the time an algorithm takes to find an element in an ordered vector with n elements, in the worst case. A naive algorithm will search from left to right, one element at a time. The worst possible scenario is when the required element is the last, so the number of comparisons is n. A better algorithm is called
binary search In computer science, binary search, also known as half-interval search, logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array. Binary search compares the target value to the m ...
. However, it requires a sorted vector. It will first check if the element is at the middle of the vector. If not, then it will check if the middle element is greater or lesser than the sought element. At this point, half of the vector can be discarded, and the algorithm can be run again on the other half. The number of comparisons will be given by :c_1=1 :c_n=1+c_ the
time complexity In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...
of which will be O(\log_2(n)).


Digital signal processing

In
digital signal processing Digital signal processing (DSP) is the use of digital processing, such as by computers or more specialized digital signal processors, to perform a wide variety of signal processing operations. The digital signals processed in this manner are ...
, recurrence relations can model feedback in a system, where outputs at one time become inputs for future time. They thus arise in
infinite impulse response Infinite impulse response (IIR) is a property applying to many linear time-invariant systems that are distinguished by having an impulse response h(t) which does not become exactly zero past a certain point, but continues indefinitely. This is in ...
(IIR)
digital filter In signal processing, a digital filter is a system that performs mathematical operations on a sampled, discrete-time signal to reduce or enhance certain aspects of that signal. This is in contrast to the other major type of electronic filter, t ...
s. For example, the equation for a "feedforward" IIR
comb filter In signal processing, a comb filter is a filter implemented by adding a delayed version of a signal to itself, causing constructive and destructive interference. The frequency response of a comb filter consists of a series of regularly spaced no ...
of delay T is: :y_t = (1 - \alpha) x_t + \alpha y_, where x_t is the input at time t, y_t is the output at time t, and \alpha controls how much of the delayed signal is fed back into the output. From this we can see that :y_t = (1 - \alpha) x_t + \alpha ((1-\alpha) x_ + \alpha y_) :y_t = (1 - \alpha) x_t + (\alpha-\alpha^2) x_ + \alpha^2 y_ etc.


Economics

Recurrence relations, especially linear recurrence relations, are used extensively in both theoretical and empirical economics. In particular, in macroeconomics one might develop a model of various broad sectors of the economy (the financial sector, the goods sector, the labor market, etc.) in which some agents' actions depend on lagged variables. The model would then be solved for current values of key variables (
interest rate An interest rate is the amount of interest due per period, as a proportion of the amount lent, deposited, or borrowed (called the principal sum). The total interest on an amount lent or borrowed depends on the principal sum, the interest rate, th ...
, real
GDP Gross domestic product (GDP) is a monetary measure of the market value of all the final goods and services produced and sold (not resold) in a specific time period by countries. Due to its complex and subjective nature this measure is ofte ...
, etc.) in terms of past and current values of other variables.


See also

* Holonomic sequences *
Iterated function In mathematics, an iterated function is a function (that is, a function from some set to itself) which is obtained by composing another function with itself a certain number of times. The process of repeatedly applying the same function is ...
*
Orthogonal polynomials In mathematics, an orthogonal polynomial sequence is a family of polynomials such that any two different polynomials in the sequence are orthogonality, orthogonal to each other under some inner product. The most widely used orthogonal polynomial ...
*
Recursion Recursion (adjective: ''recursive'') occurs when a thing is defined in terms of itself or of its type. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in mathematics ...
*
Recursion (computer science) In computer science, recursion is a method of solving a computational problem where the solution depends on solutions to smaller instances of the same problem. Recursion solves such recursive problems by using functions that call themselves ...
*
Lagged Fibonacci generator A Lagged Fibonacci generator (LFG or sometimes LFib) is an example of a pseudorandom number generator. This class of random number generator is aimed at being an improvement on the 'standard' linear congruential generator. These are based on a gene ...
*
Master theorem (analysis of algorithms) In the analysis of algorithms, the master theorem for divide-and-conquer recurrences provides an asymptotic analysis (using Big O notation) for recurrence relations of types that occur in the analysis of many divide and conquer algorithms. The app ...
*
Circle points segments proof The number of and for first 6 terms of Moser's circle problem In geometry, the problem of dividing a circle into areas by means of an inscribed polygon with ''n'' sides in such a way as to ''maximise'' the number of areas created by the edges an ...
*
Continued fraction In mathematics, a continued fraction is an expression (mathematics), expression obtained through an iterative process of representing a number as the sum of its integer part and the multiplicative inverse, reciprocal of another number, then writ ...
*
Time scale calculus In mathematics, time-scale calculus is a unification of the theory of difference equations with that of differential equations, unifying integral and differential calculus with the calculus of finite differences, offering a formalism for studying hy ...
*
Combinatorial principles In proving results in combinatorics several useful combinatorial rules or combinatorial principles are commonly recognized and used. The rule of sum, rule of product, and inclusion–exclusion principle are often used for enumerative purposes. Bij ...
*
Infinite impulse response Infinite impulse response (IIR) is a property applying to many linear time-invariant systems that are distinguished by having an impulse response h(t) which does not become exactly zero past a certain point, but continues indefinitely. This is in ...
*
Integration by reduction formulae In integral calculus, integration by reduction formulae is method relying on recurrence relations. It is used when an expression containing an integer parameter, usually in the form of powers of elementary functions, or products of transcendental ...
*
Mathematical induction Mathematical induction is a method for proving that a statement ''P''(''n'') is true for every natural number ''n'', that is, that the infinitely many cases ''P''(0), ''P''(1), ''P''(2), ''P''(3), ...  all hold. Informal metaphors help ...


References


Footnotes


Bibliography

* * * * *
Thomas H. Cormen Thomas H. Cormen is the co-author of ''Introduction to Algorithms'', along with Charles Leiserson, Ron Rivest, and Cliff Stein. In 2013, he published a new book titled '' Algorithms Unlocked''. He is a professor of computer science at Dartmout ...
,
Charles E. Leiserson Charles Eric Leiserson is a computer scientist, specializing in the theory of parallel computing and distributed computing, and particularly practical applications thereof. As part of this effort, he developed the Cilk multithreaded language. ...
,
Ronald L. Rivest Ronald Linn Rivest (; born May 6, 1947) is a cryptographer and an Institute Professor at MIT. He is a member of MIT's Department of Electrical Engineering and Computer Science (EECS) and a member of MIT's Computer Science and Artificial Inte ...
, and
Clifford Stein Clifford Seth Stein (born December 14, 1965), a computer scientist, is a professor of industrial engineering and operations research at Columbia University in New York, NY, where he also holds an appointment in the Department of Computer Scien ...
. ''
Introduction to Algorithms ''Introduction to Algorithms'' is a book on computer programming by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. The book has been widely used as the textbook for algorithms courses at many universities and is co ...
'', Second Edition. MIT Press and McGraw-Hill, 1990. . Chapter 4: Recurrences, pp. 62–90. * * * chapter 7. * Chapter 9.1: Difference Equations. * * at EqWorld - The World of Mathematical Equations. * at EqWorld - The World of Mathematical Equations. *


External links

* * *
OEIS The On-Line Encyclopedia of Integer Sequences (OEIS) is an online database of integer sequences. It was created and maintained by Neil Sloane while researching at AT&T Labs. He transferred the intellectual property and hosting of the OEIS to the ...
index to a few thousand examples of linear recurrences, sorted by order (number of terms) and signature (vector of values of the constant coefficients) {{Authority control Algebra Combinatorics